(in-package "ACL2")
(include-book "../../include/src/avl-integer-keys")
(include-book "avl-utils")

;;;Utilities for querying and manipulating grids
;;;represented by AVL trees.
;;;
;;;For the most part these functions have a very similar form.
;;;
;;;"get" functions return t if the cell they're referring to is
;;;     alive, nil otherwise
;;;"set" functions alter a grid by setting the live status
;;;     of a cell to the requested value, and return the altered
;;;     grid
;;;"toggle" functions flip a cell from being alive to dead or 
;;;     vice-versa
;;;"get-cell" and "set-cell" are like get and set, but 
;;;     take a cell object instead of an x and y value 
;;;     (these don't exist for elementary grids)
;;;
;;;Many of these functions will be different for lifelike and
;;;elementary grids. These are distinguished by having "lifelike"
;;;or "elementary" in the function names. Some of these also
;;;have a "type" version where the value of the type parameter
;;;determines which function to call. t corresponds to lifelike and nil
;;;corresponds to elementary. Use of the "type" version
;;;is not recommended.


(defun empty-lifelike-grid () 
        (empty-tree))

(defun empty-elementary-grid () 
        (empty-tree))

(defun lifelike-grid-get (grid x y)
  (if (avl-retrieve (cdr (avl-retrieve grid x)) y) t nil))

(defun lifelike-grid-get-cell (grid c)
  (lifelike-grid-get grid (cell-x c) (cell-y c)))

(defun lifelike-grid-set (grid x y val)
        (if val
                (nested-avl-insert grid x y val)
                (nested-avl-delete grid x y)))

(defun lifelike-grid-set-cell (grid cell val)
    (lifelike-grid-set grid (cell-x cell) (cell-y cell) val))

(defun lifelike-grid-toggle (grid x y)
        (let* ((val (not (lifelike-grid-get grid x y))))
                (lifelike-grid-set grid x y val)))

(defun elementary-grid-get (grid pos)
    (cdr (avl-retrieve grid pos)))

(defun elementary-grid-get-cell (grid c)
  (elementary-grid-get grid (cell-x c)))

(defun elementary-grid-set (grid pos val)
    (if val 
        (avl-insert grid pos val)
        (avl-delete grid pos)))

(defun elementary-grid-toggle (grid pos)
    (let* ((val (not (elementary-grid-get grid pos))))
        (elementary-grid-set grid pos val)))

(defun grid? (form)
    (tree? form))

(defun type-get (type_ grid x y)
  (if type_
      (lifelike-grid-get grid x y)
      (elementary-grid-get grid x)))

(defun type-get-cell (type_ grid c)
  (if type_
      (lifelike-grid-get-cell grid c)
      (elementary-grid-get-cell grid c)))

(defun set-type (type_ grid x y val)
  (if type_
      (lifelike-grid-set grid x y val)
      (elementary-grid-set grid x val)))

;;Helper for elementary-grid-get-all-live-cells
;; flattened-grid: list of unprocessed cons pairs whose
;;      first element is a position (i.e., the result of
;;      calling avl-flatten on an elementary grid)
;; acc: list of the positions of cons pairs already processed
;;
;; returns acc after exhausting flattened-grid
(defun elementary-grid-grab-positions* (flattened-grid acc)
    (if (endp flattened-grid)
        acc
        (let* ((pos (caar flattened-grid))
               (rest-flattened-grid (cdr flattened-grid)))
            (elementary-grid-grab-positions* rest-flattened-grid
                (cons pos acc)))))

;;returns list of all live cells (in
;;sorted order)
(defun elementary-grid-get-all-live-cells (elem-grid)
    (let* ((flattened (avl-flatten elem-grid)))
        (elementary-grid-grab-positions* flattened nil)))

(defun lifelike-grid-set-multiple-cells (grid cells val)
   (if (endp cells)
       grid
       (lifelike-grid-set-multiple-cells
        (lifelike-grid-set-cell grid (car cells) val)
        (cdr cells)
        val)))

(defun elementary-grid-set-multiple (grid ints val)
  (if (endp ints)
      grid
      (elementary-grid-set-multiple
        (elementary-grid-set grid (car ints) val)
        (cdr ints)
        val)))


;;Get a list of the y elements of cells
(defun get-ys* (cells)
   (if (endp cells)
       nil
    	  (cons (cell-y (car cells)) (get-ys* (cdr cells)))))

;;Get minimum element of list or curr-min
;;if min is smaller than all elements
(defun min-list-rec* (lst curr-min)
  (if (endp lst)
    curr-min
    (if (< (car lst) curr-min)
      (min-list-rec* (cdr lst) (car lst))
      (min-list-rec* (cdr lst) curr-min))))

;;Get minimum element of list, or nil if
;;list is empty.
(defun min-list* (lst)
  (min-list-rec* (cdr lst) (car lst)))

;;Get max element of list or curr-max
;;if max is larger than all list elements
(defun max-list-rec* (lst curr-max)
  (if (endp lst)
    curr-max
    (if (> (car lst) curr-max)
      (max-list-rec* (cdr lst) (car lst))
      (max-list-rec* (cdr lst) curr-max))))

;;Get maximum element of list, or nil if
;;list is empty.
(defun max-list* (lst)
  (max-list-rec* (cdr lst) (car lst)))

;;Given a grid (lifelike OR elementary)
;;get the farthest left cell that's alive
(defun get-left-bound* (gr)
   (car (avl-min gr)))

;;Given a grid (lifelike OR elementary)
;;get the farhtest right cell that's alive
(defun get-right-bound* (gr)
   (car (avl-max gr)))

;;given a list of cells
;;get the one with the highest y
(defun get-top-bound* (cell-lst)
  (max-list* (get-ys* cell-lst)))

;;given a list of cells, get the one with
;;the lowest y
(defun get-bottom-bound* (cell-lst)
  (min-list* (get-ys* cell-lst)))
 
;;representation of bounds for lifelike grid
(defstructure ll-bounds
    (left)
    (right)
    (top)
    (bottom))

;;bounds for elem grid
(defstructure el-bounds
  (left)
  (right))

;;Get boundaries (furthest extents)
;;of an elementary grid
(defun get-el-bounds (gr)
  (el-bounds 
    (get-left-bound* gr)
    (get-right-bound* gr)))

;;get boundaries (furthest extents)
;;of a lifelike grid
(defun get-ll-bounds (gr)
   (let* ((cell-lst (nested-avl-flatten-to-cells gr)))
	  (ll-bounds
	    (get-left-bound* gr)
	    (get-right-bound* gr)
	    (get-top-bound* cell-lst)
	    (get-bottom-bound* cell-lst))))

;;Flatten grid based on ruletpye
(defun flatten-grid (grid ruletype)
   (if (equal ruletype "lifelike")
       (nested-avl-flatten-to-cells grid)
       (elementary-grid-get-all-live-cells grid)))
